W11. Основы теории графов, деревья и леса, остовные деревья, алгоритмы MST
1. Краткое содержание
1.1 Основы теории графов
Graph theory изучает отношения между объектами. Graph \(G=(V,E)\) состоит из vertices (вершин, nodes) и edges (рёбер), моделирующих попарные связи.
1.1.1 Терминология
Для simple undirected graph: \(E \subseteq \{\{u,v\}\mid u,v\in V, u\neq v\}\) — без loops и без multiple edges; рёбра неориентированы (в отличие от directed graphs / digraphs). Ребро \(\{x,y\}\) часто пишут \(xy\), \(x\text{--}y\) или \((x,y)\).
1.1.2 Смежность и инцидентность
Adjacency вершин: \(x,y\) adjacent / neighbors, если есть ребро \(xy\). Incidence: вершина \(v\) incident ребру \(e\), если \(v\) — конец \(e\); два конца — endvertices / ends. Adjacency рёбер: рёбра adjacent, если делят общую вершину.
1.1.3 Изоморфизм графов
Графы isomorphic (\(G\simeq G'\)), если есть биекция \(\phi:V\to V'\) с сохранением рёбер: \[(x,y)\in E \iff (\phi(x),\phi(y))\in E'\] Биекция \(\phi\) — isomorphism. Доказать неизоморфность можно инвариантом (степенная последовательность, число циклов, связность).
1.1.4 Степени вершин
Neighborhood: \(N_G(v)=\{u\in V_G\mid (v,u)\in E_G\}\). Degree \(d_G(v)=|N_G(v)|\). Degree sequence — список степеней, обычно по неубыванию.
1.2 Лемма о рукопожатиях (Handshaking Lemma)
\[\sum_{v\in V_G} d_G(v)=2|E_G|\] Каждое ребро учитывается в сумме степеней дважды. Следствие: сумма степеней чётна (например, степени \(2,3,4\) у трёх вершин невозможны).
1.3 Прогулки, пути, связность
1.3.1 Walks и paths
Walk — последовательность вершин, где соседние соединены ребром. Closed walk — начало и конец совпадают. Path — walk без повторения рёбер. Cycle — замкнутый path (кроме совпадения первой и последней вершины).
1.3.2 Связность
Connected graph — между любыми двумя вершинами есть path. Иначе disconnected. Subgraph \(G'=(V',E')\): \(V'\subseteq V\), \(E'\subseteq E\). Component — максимальный связный подграф.
1.4 Деревья и леса
1.4.1 Определения
Tree — связный граф без циклов. Forest — граф без циклов (не обязательно связный); дизъюнктное объединение деревьев.
1.4.2 Применения
Иерархии, файловые системы, decision trees, game trees и др.
1.4.3 Эквивалентные характеризации дерева
Для графа \(T\) эквивалентно: (1) дерево; (2) любые две вершины соединены единственным путём; (3) minimally connected; (4) maximally acyclic.
1.4.4 Свойства
У дерева с \(|V|\ge2\) есть хотя бы два leaf (степень 1). Теорема: связный \(G\) с \(n\) вершинами и \(e\) рёбрами — дерево тогда и только тогда, когда \(n=e+1\).
1.5 Остовные деревья (spanning trees)
1.5.1 Определение
Spanning tree связного \(G=(V,E)\) — подграф \((V,E')\), дерево на всех вершинах \(V\). Любой связный граф имеет хотя бы один остов: пока есть цикл, удаляем ребро из цикла (связность сохраняется).
1.5.2 Жадное построение
Пока есть цикл — удалить ребро из цикла; когда циклов нет — получится остов.
1.5.3 Spanning Tree Protocol (STP)
В сетях Ethernet STP строит остов, убирая петли на уровне логической топологии.
1.6 Взвешенные графы и MST
1.6.1 Взвешенные графы
Weighted graph: веса на рёбрах \(f:E\to\mathbb R\) (edge-weighted) или на вершинах (vertex-weighted). Total weight остова — сумма весов его рёбер.
1.6.2 Minimal spanning tree (MST)
Найти остов минимального суммарного веса. Классические greedy-алгоритмы: Kruskal’s algorithm и Prim’s algorithm.
1.7 Алгоритм Краскала
Сортировка рёбер по весу; добавляем ребро, если не возникает цикл; останов при \(n-1\) рёбре. Для несвязного \(G\) получается minimal spanning forest. Для проверки циклов используют union-find (disjoint-set).
1.8 Алгоритм Прима
Дерево «растёт» из одной вершины: на каждом шаге добавляется ребро минимального веса из текущего дерева к новой вершине. Отличие от Краскала: у Прима одно растущее дерево. Для эффективности на каждом шаге удобна priority queue (min-heap).
1.9 Стандартные семейства графов
Complete graph \(K_n\): \(\binom{n}{2}\) рёбер, степень \(n-1\). Cycle \(C_n\) (\(n\ge3\)): все степени 2. Wheel \(W_n\): цикл \(C_n\) плюс центр, соединённый со всеми вершинами цикла. Bipartite graph: \(V=U\sqcup V\), рёбра только между \(U\) и \(V\). Complete bipartite \(K_{n,m}\): \(nm\) рёбер.
2. Определения
- Graph — пара \(G=(V,E)\).
- Simple graph — без петель и кратных рёбер.
- Undirected graph — рёбра неориентированы.
- Vertices / edges — объекты и связи.
- Adjacent vertices, incident, endvertices, degree, neighborhood, degree sequence.
- Isomorphic graphs, isomorphism.
- Walk, closed walk, path, cycle.
- Connected / disconnected graph, subgraph, component.
- Tree, forest, leaf, spanning tree.
- Weighted graph, total weight, minimal spanning tree.
- \(K_n\), \(C_n\), \(W_n\), bipartite, \(K_{n,m}\).
3. Формулы
- Handshaking Lemma: \(\sum_{v\in V_G} d_G(v)=2|E_G|\)
- \(K_n\): \(|E|=\binom{n}{2}=\dfrac{n(n-1)}2\), степень \(n-1\)
- \(C_n\): степени 2, \(|E|=n\)
- \(K_{n,m}\): \(|E|=nm\)
- Дерево: связный \(G\) с \(n\) вершинами — дерево \(\iff\) \(|E|=n-1\)
- Лес: \(n\) вершин, \(k\) компонент \(\Rightarrow\) \(|E|=n-k\)
- Число простых графов порядка \(n\): \(2^{\binom{n}{2}}\)
- Двудольные при фиксированных долях \(|U|=n\), \(|V|=m\): \(2^{nm}\)
4. Примеры
4.1. Рисунок графа по множествам (Лаба 9, Задание 1a)
\(V=\{1,\dots,6\}\), \(E=\{\{1,2\},\{2,3\},\{2,4\},\{2,5\},\{3,6\},\{4,5\},\{5,6\}\}\). Нарисовать граф.
Показать решение
Суть: расставить шесть вершин и соединить рёбрами пары из \(E\). Вершина 2 — «хаб» степени 4; есть циклы \(2\text{-}4\text{-}5\text{-}2\) и \(2\text{-}3\text{-}6\text{-}5\text{-}2\).
Ответ: любой рисунок с указанными рёбрами корректен; на иллюстрации в материале — один из вариантов.4.2. Степенная последовательность (Лаба 9, Задание 1b)
Для графа из 4.1 — степени всех вершин.
Показать решение
\(d(1)=1\), \(d(2)=4\), \(d(3)=2\), \(d(4)=2\), \(d(5)=3\), \(d(6)=2\); по неубыванию \((1,2,2,2,3,4)\); сумма \(14=2\cdot7\).
Ответ: \((1,2,2,2,3,4)\).4.3. Вершины нечётной степени (Лаба 9, Задание 1c)
Показать решение
Нечётные степени: \(1\) и \(3\) — две вершины (число нечётных степеней всегда чётно).
Ответ: 2 вершины.4.4. Графы по степенной последовательности (Лаба 9, Задание 2)
(a) \((2,2,2,2,2)\) (b) \((2,2,2,2,2,2)\) (c) \((3,3,3,3)\) (d) \((1,2,3,4,5)\) — нарисовать простой граф (если возможно); единственность с точностью до изоморфизма?
Показать решение
(a) 2-регулярный граф на 5 вершинах — единственный связный вариант \(C_5\) (с точностью до изоморфизма). (b) \(C_6\) и \(C_3\cup C_3\) — неизоморфны → не единственен. (c) единственный простой 3-регулярный на 4 вершинах — \(K_4\). (d) сумма степеней \(15\) нечётна — графа нет.
Ответ: (a) \(C_5\); (b) не уникален; (c) \(K_4\); (d) невозможно.4.5. Рёбра в \(K_n\) (Лаба 9, Задание 3a)
Показать решение
Пар вершин \(\binom{n}{2}\); по лемме о рукопожатиях \(n(n-1)/2\).
Ответ: \(\dfrac{n(n-1)}2\).4.6. Число простых графов порядка \(n\) (Лаба 9, Задание 3b)
Показать решение
Независимо для каждой из \(\binom{n}{2}\) потенциальных рёбер: в ребро или нет → \(2^{\binom{n}{2}}\).
Ответ: \(2^{\binom{n}{2}}\).4.7. Рёбра в \(K_{n,m}\) (Лаба 9, Задание 4a)
Показать решение
Каждая из \(n\) вершин первой доли смежна со всеми \(m\) вершинами второй → \(nm\).
Ответ: \(nm\).4.8. Двудольные графы при фиксированных долях (Лаба 9, Задание 4b)
Показать решение
\(nm\) потенциальных рёбер между долями, каждое есть/нет → \(2^{nm}\).
Ответ: \(2^{nm}\).4.9. Изоморфизм: несколько случаев (Лаба 9, Задание 5)
Показать решение
(a) Оба 2-регулярны на 5 вершинах — \(C_5\); изоморфны; пример \(\phi(u_1)=v_1\), \(\phi(u_2)=v_3\), \(\phi(u_3)=v_5\), \(\phi(u_4)=v_2\), \(\phi(u_5)=v_4\). (b) Степенная \((3,3,3,3,4)\) совпадает, но окрестность единственной вершины степени 4 разная (в одном графе смежна со всеми, в другом — не со всеми) → не изоморфны. (c) Оба \(C_7\) → изоморфны. (d) Разное число рёбер (7 vs 6) → не изоморфны.4.10. Когда \(K_n\) и \(K_{n,m}\) — деревья? (Лаба 9, Задание 6)
Показать решение
(a) \(\dfrac{n(n-1)}2=n-1\) даёт \(n=1\) или \(n=2\); при \(n\ge3\) есть \(C_3\). (b) \(nm=n+m-1\iff(n-1)(m-1)=0\) — звезда при \(n=1\) или \(m=1\).
Ответ: (a) \(n\in\{1,2\}\); (b) \(n=1\) или \(m=1\).4.11. MST: Краскал и Прим (Лаба 9, Задание 7)
(a) Краскал (b) Прим; показать шаги.
Показать решение
По рисунку с весами \((a,b,1)\), \((c,d,1)\), \((a,e,2)\), \((e,d,2)\), \((b,c,3)\), \((b,e,3)\), \((a,c,4)\): сортировка по весу, Краскал добавляет \((a,b)\), \((c,d)\), \((a,e)\), затем \((e,d)\) (соединяет компоненты без цикла), дальше рёбра веса 3 и 4 дают циклы — пропуск. MST из четырёх рёбер суммарного веса \(1+1+2+2=6\) (например \(\{(a,b),(c,d),(a,e),(e,d)\}\)). Прим из \(e\): \((e,a)\), \((a,b)\), \((e,d)\), \((d,c)\) — тот же вес \(6\).
Ответ: минимальный суммарный вес 6 (конкретный набор рёбер может совпадать с одним из вариантов выше).4.12. Все остовные деревья (Лаба 9, Задание 7a)
Тот же \(G\), что в 4.1 — перечислить идею всех остовов.
Показать решение
Остов: 6 вершин, 5 рёбер; из 7 рёбер удаляют пару, разрушающую все циклы (\(2\text{-}4\text{-}5\text{-}2\) и \(2\text{-}3\text{-}6\text{-}5\text{-}2\)), сохраняя связность. Полный перебор пар удалений даёт все остовы.
Ответ: остовы получаются удалением подходящих двух рёбер; например удаление \(\{4,5\}\) и \(\{3,6\}\) даёт остов.4.13. Неизоморфные остовы (Лаба 9, Задание 7b)
Показать решение
Разные степенные последовательности дерева-остова дают неизоморфные остовы, напр. \((1,1,1,2,2,3)\) vs \((1,1,1,1,2,2)\).
Ответ: неизоморфные остовы существуют; сравнивайте степенные последовательности.4.14. Все графы порядка 3 (Лаба 9, Задание 8)
Показать решение
\(0\ldots3\) рёбер дают 4 неизоморфных типа: пустой, одно ребро, путь \(P_3\), треугольник \(K_3\).
Ответ: 4 класса до изоморфизма.4.15. Связные графы порядка 4 (Лаба 9, Задание 9)
Показать решение
По числу рёбер \(3\ldots6\): два дерева (\(P_4\), звезда \(K_{1,3}\)), \(C_4\), «лапа», \(K_4\) без ребра, \(K_4\) — 6 неизоморфных связных графов.
Ответ: 6.4.16. Краскал на взвешенном графе (Лекция 9, Пример 1)
Показать решение
Суть: Kruskal’s algorithm — жадно добавлять рёбра по возрастанию веса, пропуская рёбра, создающие цикл, пока не получится остов на 6 вершинах (5 рёбер). Для графа на рисунке в остов входят веса \(3,4,5,5,6\); сумма \(3+4+5+5+6=23\).
Ответ: MST с суммарным весом 23.4.17. Степени в \(K_1,\dots,K_4\) (Туториал 9, Задание 1)
Показать решение
В \(K_n\) степень каждой вершины \(n-1\).
Ответ: \(K_1:(0)\); \(K_2:(1,1)\); \(K_3:(2,2,2)\); \(K_4:(3,3,3,3)\).4.18. Степени в \(C_3,\dots,C_6\) (Туториал 9, Задание 2)
Показать решение
У \(C_n\) все степени 2.
Ответ: для любого \(n\) последовательность из \(n\) двоек.4.19. Степени в \(W_3,\dots,W_6\) (Туториал 9, Задание 3)
Показать решение
Центр степени \(n\), вершины цикла степени 3.
Ответ: \(W_3:(3,3,3,3)\); \(W_4:(3,3,3,3,4)\); \(W_5:(3,3,3,3,3,5)\); \(W_6:(3,3,3,3,3,3,6)\).4.20. Степени в \(K_{3,5}\) и \(K_{2,6}\) (Туториал 9, Задание 4)
Показать решение
\(K_{3,5}\): три вершины степени 5, пять степени 3 → \((3,3,3,3,3,5,5,5)\). \(K_{2,6}\): шесть степени 2, две степени 6.
Ответ: \(K_{3,5}\): \((3,3,3,3,3,5,5,5)\); \(K_{2,6}\): \((2,2,2,2,2,2,6,6)\).4.21. Степени \((1,3,4,5)\) (Туториал 9, Задание 5)
Показать решение
Сумма \(13\) нечётна — противоречит лемме о рукопожатиях.
Ответ: такого графа нет.4.22. Изоморфизм двух графов (Туториал 9, Задание 6)
Показать решение
Оба — \(C_4\) с разной «укладкой»; изоморфизм, например \(\phi(u_1)=v_1\), \(\phi(u_2)=v_2\), \(\phi(u_3)=v_4\), \(\phi(u_4)=v_3\).
Ответ: да, \(G_1\simeq G_2\).4.23. Неизоморфизм (Туториал 9, Задание 7)
Показать решение
Степенные последовательности \((3,3,3,3)\) и \((2,2,3,3)\) различаются.
Ответ: нет, \(G_1\not\simeq G_2\).4.24. Все остовы графа из 4 вершин и 5 рёбер (Туториал 9, Задание 8)
Решение (рисунок): 
Показать решение
Удаляем 2 из 5 рёбер, сохраняя связность без цикла — 8 остовов; по структуре два класса: путь \(P_4\) (степени \(1,1,2,2\)) и звезда \(K_{1,3}\) (\(1,1,1,3\)).
Ответ: 8 остовов, 2 класса изоморфизма.4.25. Прим на взвешенном графе (Туториал 9, Задание 9)
Показать решение
Жадный шаг Prim’s algorithm: стартуем с верхней средней вершины; последовательно добавляем минимальные рёбра, выходящие из текущего дерева (\(3\), затем \(5\), \(5\), \(3\), \(4\)), пока не охватим все вершины — суммарный вес 20.
Ответ: MST суммарного веса 20.